\documentclass[a4paper,12pt]{article} 
\usepackage[italian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath,stmaryrd,amsthm}
\usepackage{graphicx}
\usepackage{multirow}
%\usepackage{url}
\usepackage{textcomp}
\usepackage{booktabs}
%\usepackage{glossary}
\usepackage{setspace}
\usepackage{listings}
\usepackage{courier}
\usepackage[usenames,dvipsnames]{color}
\usepackage{hyperref}
\usepackage{algorithm}
\usepackage{algpseudocode}


%enable subsection number
\setcounter{secnumdepth}{4}
\setcounter{tocdepth}{4}

\lstset{
%basicstyle=\small,
basicstyle=\footnotesize\ttfamily,
commentstyle=\textit,
showstringspaces=false,
frame=trbl,
linewidth=350px
}

\addto\captionsitalian{%
\renewcommand{\lstlistingname}{Tabella}}

 \begin{document}

\begin{center}
\normalsize
\includegraphics[width=.35\columnwidth]{immagini/unipd_logo} \\ \bigskip
\rmfamily\normalfont{Relazione di Progetto} \\ \bigskip
\begingroup
\rmfamily\normalfont\color{Maroon}{\Large Fuzzy-CSP Generator\&Solver} \\ \bigskip
\endgroup

\begin{tabular}{cc}
{\Large Federico Serafini}          & {\Large Lorenzo Tessari} \\
federico.serafini@studenti.unipd.it & lorenzo.tessari@studenti.unipd.it \\
Matricola: 1013995                  & Matricola: xxxxxxx
\end{tabular}

\end{center}

\bigskip
\section{Introduzione}

La programmazione a vincoli, detta anche programmazione con vincoli o constraint è un paradigma di programmazione dove le relazioni fra variabili possono essere dichiarate in forma di vincoli. I vincoli differiscono dalle primitive normalmente definite dagli altri linguaggi di programmazione per il fatto che non specificano azioni singole da eseguire passo-passo, ma piuttosto si limitano a specificare le proprietà di cui deve essere dotata la soluzione da trovare. I vincoli usati possono essere di vari tipi: quelli basati sul cosiddetto problema di soddisfacimento di vincoli (Constraint satisfaction problem o CSP), quelli risolvibili mediante l'algoritmo del Simplesso (Simplex Algorithm) ed altri. I vincoli da applicare possono essere forniti embedded nel linguaggio di programmazione, oppure in librerie separate.

La programmazione a vincoli iniziò come programmazione logica a vincoli, introducendo vincoli integrati in un programma di tipo logico. Questa variante della programmazione logica fu opera di Jaffar e Lassez, che, nel 1987, svilupparono una classe di vincoli specificatamente progettata per essere usata nel linguaggio Prolog II. La prime implementazioni di programmazione logica a vincoli furono Prolog III, CLP(R), e CHIP. Attualmente esistono molti interpreti per programmi logici a vincoli, come per esempio GNU Prolog.

Nei linguaggi imperativi, tuttavia, i vincoli sono implementati principalmente mediante i cosiddetti constraint solving toolkits, che sono librerie separate, fornite insieme al linguaggio. ILOG CP Optimizer, è un esempio è di queste librerie per C++, Java e .NET.

\subsection{CSP}

Molti problemi nell'ambito dell'Intelligenza Artificiale sono classificabili come Problemi di Soddisfacimento di Vincoli \textit{(Constraint Satisfaction Problem o CSP)}; fra questi citiamo problemi di complessità combinatoria, di allocazione di risorse, pianificazione e ragionamento temporale. Questi problemi possono essere risolti efficientemente attraverso tecniche ben note di risoluzione di CSP.

Formalmente, un CSP può essere definito su un insieme finito di variabili $(X_1, X_2, \dots, X_n)$ i cui valori appartengono a domini finiti di definizione $(D_1, D_2, \dots, D_n)$ e su un insieme di vincoli. Un vincolo su un insieme di variabili è una restrizione dei valori che le variabili possono assumere simultaneamente. Concettualmente, un vincolo può essere visto come un insieme che contiene tutti i valori che le variabili possono assumere contemporaneamente: un vincolo tra $k$ variabili $c(X_{i_1},X_{i_2},\dots,X_{i_k})$ è un sottoinsieme del prodotto cartesiano dei domini delle variabili coinvolte $D_{i_1},D_{i_2},\dots,D_{i_k}$ che specifica quali valori delle variabili sono compatibili con le altre. Questo insieme può essere rappresentato in molti modi, per esempio per mezzo di matrici, equazioni, disuguaglianze o relazioni. Una soluzione ad un CSP è un assegnamento di valori alle variabili che soddisfi tutti i vincoli.

Si cita brevemente come esempio noto il problema delle 8 regine, ovvero disporre su una scacchiera 8 regine in modo che non si attachino a vicenda.

\subsubsection{Fuzzy CSP}
In molti casi reali può essere utile avere un modello in cui è possibile associare ai vincoli dei gradi di libertà, o meglio, dei gradi di preferenza, e non solamente la proprietà vincolo rispettato/violato.
Infatti in questi casi i CSP classici risultano essere troppo restrittivi, poiché non sono in grado di rappresentare delle preferenze associate ai vincoli; è principalmente per questo motivo che sono stati introdotti i \textit{CSP fuzzy}.

Questi si basano sulla teoria degli insiemi fuzzy; i vincoli fuzzy rappresentano la prima estensione della nozione classica di vincoli, in grado di rappresentare esplicitamente delle preferenze.
Un vincolo classico può essere visto come un insieme di valori delle variabili del problema, ovvero di valori consentiti per ottenere una soluzione del problema.
Nel framework fuzzy, un vincolo non è più un insieme di valori, ma è invece un insieme \textit{fuzzy} di valori: per ogni assegnamento delle variabili è possibile definire in che misura è presente nell'insieme; in altre parole, qual è il grado di appartenenza (\textit{preferenza}) dell'assegnamento in esame.

Con questo modello quindi è possibile rappresentare delle combinazioni di valori delle variabili che fanno parte di un vincolo, ammesse parzialmente.
La \textit{funzione di appartenenza} $\mu_E$ di un insieme fuzzy $E$ associa un numero reale compreso tra 0 e 1 per ogni possibile elemento di $E$.
Quindi, se consideriamo ogni vincolo come insieme fuzzy, possiamo associare ad ogni assegnamento un valore reale, compreso tra 0 ed 1, dato dalla funzione di appartenenza.
In questo contesto un CSP classico può essere rappresentato permettendo soltanto, per la funzione di appartenenza, il valore 1 (vincolo rispettato) e il valore 0 (vincolo violato).

Come per i CSP classici, anche per i CSP fuzzy una soluzione è ottenuta quando tutti i vincoli sono soddisfatti (preferenza maggiore di 0), quindi quando la preferenza associata ad un assegnamento completo delle variabili è maggiore di 0.
Il modo con cui si combinano tra loro più assegnamenti parziali è quello di associare, alla tupla risultante, la minima preferenza degli assegnamenti che la compongono.
La \textit{soluzione ottima} del problema, poiché valori di preferenza maggiori sono da preferire, è data dall'assegnamento globale che massimizza le preferenze minime delle sottotuple che lo compongono.
Il processo di ottimizzazione consiste quindi nel massimizzare il valore della tupla con preferenza minima consentita.

\subsection{Arc-Consistency}

Una variabile di un problema di soddisfacimento vincoli è consistente sugli archi con un altra se ciascuno dei suoi valori ammissibili è consistente con un valore ammissibile della seconda variabile. Formalmente, una variabile $x_i$ è consistente sugli archi con un altra variabile $x_j$ se, per ogni valore $a$ nel dominio di $x_i$ esiste un valore $b$ nel dominio di $x_j$ tale che $(a, b)$ soddisfa il vincolo binario tra $x_i$ e $x_j$. Un problema è consistente sugli archi se ogni variabile è consistente sugli archi con qualunque altra.

Si consideri ad esempio il vincolo $x < y$ dove le variabili variano nel dominio $\{1,3\}$. Poiché x non può mai assumere valore 3, non esiste un arco da 3 a un valore di y, per cui è possibile rimuovere tale valore. Allo stesso modo y non può mai essere 1, quindi non esistono archi e tale vincolo può essere rimosso.

Se una variabile non è consistente sugli archi con un altra, può diventarlo rimuovendo alcuni valori dal suo dominio. Questa è la forma di propagazione sui vincoli che impone la consistenza sugli archi: si toglie, dal dominio della variabile, ogni valore che non corrisponde ad un valore dell'altra variabile. Questa trasformazione mantiene la soluzione del problema, poiché i valori rimossi non fanno parte di alcuna soluzione.

La propagazione sui vincoli può rendere l'intero problema consistente sugli archi ripetendo queste rimozioni per tutte le coppie di variabili. Durante questo processo potrebbe essere necessario prendere in considerazione una coppia di variabili più di una volta. Infatti, eliminando i valori dal dominio di una variabile, altre variabili potrebbero non essere più consistenti sugli archi con quest'ultima. Per esempio, se è $x_3$ è consistente sugli archi con $x_2$ ma l'algoritmo riduce il dominio di $x_2$, la consistenza di $x_3$ con $x_2$ non è più garantita e deve quindi essere eseguita di nuovo.

\subsubsection{Fuzzy Arc-Consistency}

La \textit{fuzzy arc-consistency} è simile al arc-consistency descritta nella sezione precedente, tuttavia nel caso dei CSP fuzzy dobbiamo tenere in considerazione anche le preferenze associate agli assegnamenti.

Utilizzando l'operatore di combinazione dei vincoli fuzzy, che seleziona la preferenza minima dell'assegnamento (indicato col simbolo $\otimes$), la consistenza su un generico arco $(x_i,x_j)$ è ottenuta nel seguente modo:
\[
c_{x_i}:=(c_{x_i} \otimes c_{x_ix_j} \otimes c_{x_j})|_{x_i}
\]
dove $|_{x_i}$ è l'operatore di proiezione, definito come
\begin{align*}
se & \quad c=<f,con> \quad allora \quad c|_l = <f',l \cap con> \\
con & \quad f'(t') = max(f(t)) \quad \forall t \quad t.c. \quad t|_{l \cap con} = t'
\end{align*}

La procedura di consistenza viene applicata ad ogni arco del CSP finché non si raggiunge la stabilità, ovvero quando tutti i vincoli unari $C_{x_i}$ sono aggiornati.
Quando un valore $b \in D_i$ - con $D_i$ dominio della variabile $x_i$ - ha preferenza 0 (vincolo unario violato) allora il valore $b$ viene rimosso dal dominio $D_i$.

L'algoritmo di arc-consistency implementato è una variazione di \textit{AC-2001} \cite{}, riadattata per CSP fuzzy.

\begin{algorithm}
\caption{Euclid’s algorithm}\label{euclid}
\begin{algorithmic}[1]
\Function{FindSupports}{$i,j$}
	\ForAll{$a \in D_i$}
		\If{$S(i,a,j) \notin D_j$}
			\State $v := \mathrm{argmax}_{b \in D_j} \{C_{ij}(a,b)\}$;
			\State $\alpha := \min(C_i,C_{ij}(a,v))$;
			\State $S(i,a,j) := (v,\alpha,\mathtt{True})$;
			\State $C_i(a) := \alpha$;
			\ForAll{$b \in D_j$}
				\If{}
				\EndIf
			\EndFor
		\EndIf
	\EndFor

\EndFunction
\end{algorithmic}
\end{algorithm}

\newpage
\section{Implementazione}

L'ambiente di sviluppo scelto è stato l'$SDK\; QT\; 4.7$ con $QT\; Creator\; 2.4$ come editor. Questo Framework multipiattaforma permette in maniera semplice di avere tutto il necessario per costruire un'interfaccia grafica su cui appoggiare il nostro progetto; il linguaggio utilizzato è il c++, il quale permette di avere una migliore performance nell'esecuzione. Il codice binario fornito è per Win32, ma dato il codice sorgente è possibile compilarlo per qualsiasi piattaforma supportata dalle $QT$ (Win, Linux, Mac e con poche modifiche anche per Mobile: Harmattan, Symbian, ...).

\subsection{Classi}

Il progetto è suddiviso principalmente in due Layer: abbiamo l'interfaccia grafica ed il package per generazione e risoluzione di CSP:

\begin{itemize}
\item FuzzyCSPSolver Package\begin{itemize}
\item Binary\_costraint
\item Fcsp
\item Solver
\item Variable

\end{itemize}
\item GData
\item MainWindow
\item WGraph

\end{itemize}

\subsection{Regole generali}

Regole generali sull'implementazione
%TODO fede

\subsection{CPS Random}

%TODO fede

\subsection{Solver}

%TODO fede

\subsection{GUI}

L'interfaccia è lo strato a diretto contatto con l'utente, deve essere semplice, intuitiva e fornire a colpo d'occhio tutto il necessario per lavorare. Inoltre deve controllare che gli input dati dall'utente siano consistenti col problema ed in caso negativo indirizzarlo verso la correzione. Fornisce inoltre ad esecuzione completata un grafico sull'andamento della risoluzione del problema a seconda dei dati di partenza forniti.

\subsubsection{Classe GData}

La classe GData si occupa di mantenere i dati del problema ed i risultati dati dal solver per poi plottare a video il grafico.

\subsubsection{Classe MainWindow}

La classe MainWindow si occupa di gestire l'iterazione con l'utente, fornendogli una schermata semplice ed immediata per inserire i dati relativi al problema ed usando i relativi controlli perché i dati siano consistenti, notificando eventuali errori.

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.5]{immagini/scsp.png}
\caption{Schermata della GUI}
\label{fig: Schermata della GUI}
\end{figure}

Nel menù \textit{Options} si può selezionare la modalità parziale o completa dell'algoritmo AC2001 descritto nel capitolo 2.4.

Durante l'esecuzione viene fornita la possibilità, qualora si ritenesse necessario, di interrompere il processo; in tal caso non verrà ovviamente visualizzato nessun grafico riassuntivo.

\subsubsection{Classe WGraph}

La classe WGraph si occupa di visualizzare il grafico risultante dalla risoluzione del csp nelle varie istanze, mostrando l'andamento sia per il tempo di calcolo (medio) di ogni iterazione sia sulla percentuale di FSCP effettivamente risolvibili.

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.2]{immagini/graph.png}
\caption{Schermata del grafico finale}
\label{fig: Schermata del grafico finale}
\end{figure}

\newpage
\section{Utilizzo del programma}

Il programma fornisce principalmente due tipologie di approccio:
\begin{itemize}
\item approccio statistico
\item approccio fisso

\end{itemize}

Nel primo caso si inseriscono valori minimi/massimi nei rispettivi campi dati del gruppo $Soft\text{-}CSP\;setup$ ed un buon numero di istanze nel gruppo $Batch\;mode$; in questo modo verrà fornita una media sui risultati complessivi di problemi.\\

Nel secondo, invece, si inserisce lo stesso valore nei campi dati del gruppo $Soft\text{-}CSP\;setup$ ed un numero variabile, da 1 in su, nel campo del numero di istanze del gruppo $Batch\;mode$; essendo la generazione del csp casuale, ma partendo sempre dagli stessi parametri, può essere utile utilizzare diverse istanze per avere una stima migliore sulla data configurazione.\\

In entrambi i casi è possibile utilizzare il $batch\;mode$ settando un numero congruo per il campo incremento ed ottenere così un grafico che mostra l'andamento in tempo calcolo e percentuale problemi risolti.\\

Nel menù $options$, infine, è possibile selezionare se si vuole utilizzare la versione parziale o completa dell'AC2001 implementato; si noti che la versione completa richiede sensibilmente più tempo. Per eventuali chiarimenti sulle due modalità si rimanda al capitolo 2.4.

\newpage
\subsection{Esecuzione}

Dopo aver inserito i parametri desiderati premendo il pulsante \textit{Start} parte l'esecuzione, mostrando una barra di avanzamento e un messaggio di status che quantifica il numero di iterazioni fatte sul totale. In qualsiasi momento è possibile premere il pulsante \textit{Stop} per interrompere il processo [FIG 3].

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.5]{immagini/scsp_esec.png}
\caption{Programma in esecuzione}
\label{fig: Programma in esecuzione}
\end{figure}

Nel caso il valore del campo \textit{incremento} fosse 0, non essendo necessario plottare un grafico, viene dato un messaggio riassuntivo del risultato indicando il tempo medio di esecuzione del solver e quanti problemi sul totale erano risolvibili [FIG 4].

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.5]{immagini/scsp_noInc.png}
\caption{Risultato senza incrementi}
\label{fig: Risultato senza incrementi}
\end{figure}

\subsubsection{Grafico}

Se è stato fornito un valore maggiore di 0 nel campo $incremento$, viene plottato a video il grafico. In base alla variabile selezionata nel gruppo $Batch$ $mode$, si può vedere l'andamento del tempo calcolo medio e della percentuale di csp risolti all'aumentare del suo valore.

\begin{figure}[!tbh]
\centering
\includegraphics[scale=0.2]{immagini/graph.png}
\caption{Schermata del grafico finale (2)}
\label{fig: Schermata del grafico finale (2)}
\end{figure}
\newpage
Come da Legenda abbiamo in blu con pallini rossi in corrispondenza dei valori trovati il tempo di calcolo ed in verde l'andamento percentuale di csp risolti; si fa notare che l'apice del grafico corrisponde al 100\% di csp risolti ed il fondo lo 0\%.

\subsection{Considerazioni Finali}

%TODO integrazione fede

 \end{document}
